package sstring

// 串的模式匹配算法（真子串匹配算法）
// 串的下标从1开始，0闲置不用

// 定义数据结构，一般使用顺序串
type SString struct {
	ch     []byte // 存储串的一维数组
	length int    // 串的当前长度
}

// 初始化串时
// 从下标1位置开始所以容量的长度要是期望的长度+1
// 第一个位置可以用空格代替

// 模式匹配算法暴力解法
// 将使用模式串t与主串s从头开始的每个字符进行匹配
// 若匹配失败，则模式串的索引j回溯为1，主串的索引i回溯为i-j+2，开始下一个模式串的匹配
// 直到匹配成功为止，返回匹配成功的位置，若匹配失败返回0
// 主串长度n，模式串长度m，时间复杂度O(m*n)
// 最坏情况是共匹配了(n-m)*m+m次
func IndexBF(s, t SString) int {
	// 主串和模式串都从1开始
	i, j := 1, 1
	// 当主串的索引大于长度或者模式串的索引大于模式串的长度都是结束
	for i <= s.length && j <= t.length {
		if s.ch[i] == t.ch[j] {
			i++
			j++
		} else {
			j = 1
			i = i - j + 2
		}
	}
	if j > t.length {
		return i - t.length
	}
	return 0
}

// 模式匹配算法KMP算法解法
func IndexKMP(s, t SString, next []int) int {
	i, j := 1, 1
	for i <= s.length && j <= t.length {
		if j == 0 || s.ch[i] == t.ch[j] { // j == 0是nextval数组创建过程中与第j位各级公共前后缀长度+1位的值比较之后都不匹配时出现的，此时开始将主串的下一位与模式串的第1位比较
			i++
			j++
		} else {
			j = next[j] // 循环获取模式串的第j位各级公共前后缀长+1位的值，j = 0即不存在公共前后缀时由if j == 0退出
		}
	}
	if j > t.length {
		return i - t.length
	}
	return 0
}

// 手动求模式串的下一步数组
// 遍历模式串，分别处理每个位置与主串不同时的情况
// 1、第一个位置不同时为特例需要与主串的下一位比较，其余情况都是与主串的当前位比较，next数组值为0，表示模式串的一号位与主串的下一位(i+1)比较
// 2、第二个位置不同时，next数组值为1，因为二号位之前只有一个位置，不存在公共前后缀，所以要完整回溯，从1号位置开始比较
// 3、第n∈(n>2)个位置不同时，next数组值为公共前后缀的长度+1，也就是公共前缀的下一个
// 4、当不存在公共前后缀时，也就是公共前后缀长度为0时，next数组的值为0+1=1
// 5、第2 3 4种情况从数学抽象上来说都是一样的，为公共前后缀的长度+1

// 求下一步数组代码核心思想
// ******求next数组中第i+1个位置的值时，已知第i个位置next数组中的值了，也就是知道了模式串第i个位置之前的公共前缀加一的位置，
// ******因为公共前缀与公共后缀完全相同，所以只需要比较公共前缀加一的位置的值是否与模式串第i个位置的值相等，
// ******若相等，则表示“公共前缀与公共前缀+1位置的子模式串”等于“公共后缀与公共后缀+1(i)位置的子模式串” 则next[i+1]就等于公共前缀的长度加一，若不相等，
// ******则比较公共前缀加一位置的之前的模式串公共前缀加一位置即next[next[i]]的值与i位置的值是否相等
// ******若相等，则next[i+1]就等于此子模式串公共前缀长度加一的值。依次比较，直到子模式串不存在公共前后缀时将第一个位置的值和i位置的值相比，
// ******若相等则是next[i+1]=长度加一，若不相等，第一个位置的next值为0，则next[i+1]=0+1为1，然后开始比较下一位。
// 总结下来就是两点
// 1、求next[i+1]时，已知条件为next[1]到next[i]的值，next[i]的值即为第i个位置之前的子模式串的公共前后缀的长度+1（也是公共前缀部分的下一个值的索引值）
// 2、求next[i+1]时，就是求i+1位置之前的子模式串的公共前后缀的长度+1的值，而第i个位置之前的公共前后缀的长度的值是已知的
//    观察可得求第i+1个位置之前的子模式串公共前后缀的长度，可以比较第i个位置之前的子模式串公共前缀之后的一个值(相当于公共前缀加上之后的一个值)
//    与第i个值(相当于公共后缀加上第i个值)是否相等，若相等则得到第i+1个位置之前的公共前后缀的长度，加一即为next[i+1]的值
//    若不相等，则寻找下一级（更短的）公共前后缀，进行上述对比。当某一级公共前后缀长度为0时，只需比较第（公共前后缀长度加一）1个和第i个，若不相等，
//    则i+1之前不存在公共前后缀，则next[i+1] = 1
// 3、利用第1个位置的next[1]为0第二个位置为1，处理寻找下一级公共前后缀时的出口
// 4、模式串的最后一个值不需要考虑，因为求最后一个位置的next[]值时只对前n-1个做比较
// next数组使用模式串的下标为索引值，从1号位置开始

// 终极感悟
// getNext函数简介
// 公约: 1、将“第i位之前的子模式串的公共前后缀的长度+1”统称为“第i位的公共前后缀长度+1”
//       2、若目前求的是第i+1位的next数组的值，则将“第i位的公共前缀部分作为子模式串的模式串的公共前后缀部分”称为“较低一级的公共前后缀”
//          将被第i位的公共前后缀部分中嵌套的每个较低一级的公共前后缀称为“第i位的各级公共前后缀”
// 1、i：表示求第i+1个位置的next数组值时，已知第1个到第i个位置的next数组的值，因为第i+1位的公共前后缀长度最大就是第i位的公共前后缀长度+1，所以可以利用第i位
//    与第i位的公共前后缀长度+1位的值作比较，若不同，依次与较低一级的公共前后缀长度+1位置的值作比较
// 2、next[1]=0, i = 1: next[1]=0表示第一个位置的值固定就是零，当模式匹配算法中拿到next数组中的值为0时，会将主串的位置加1。
//                      i = 1 与上述条件结合就表示当前是求第i+1=2个位置的next数组的值
// 4、j, j==0: 当j=0时，表示第i+1位不存在公共前后缀的情况，所以第i+1位next数组的值next[++i] = ++j
//             j != 0时，表示第i位的公共前缀长度+1位的值
//             j == 0 当第i位的值与第i位的各级公共前缀长度+1位置的值比较后都不相同，且第一个位置与第i位的值也不相同时，j会被置为0，就出现了j == 0的情况
// 5、t.ch[i] == t.ch[j]：当第i位的值等于第i位的某一级公共前缀长度+1位的值时，此条件成立，可以通过next[++i] = ++j得到next[i+1]的值
// 6、else j=next[j]: 循环获取较低一级的公共前后缀长度+1的值，直到j=0时退出
func getNext(t SString) []int {
	// t.ch从索引为1的位置开始
	next := make([]int, t.length+1)
	next[1] = 0
	i, j := 1, 0
	for i < t.length {
		if j == 0 || t.ch[i] == t.ch[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}
	return next
}

// getNextval是getNex的改进版
// getNext的做法：求第i+1个位置的next数组值时，是因为第i+1个位置的值与主串当前位置的值不相等，此时要将模式串的“第i+1位的公共前缀长度+1”位的值开始与主串的当前位置比较
// getNext存在的问题：此时比较时，若模式串的“第i+1位的公共前缀长度+1”位的值与第i+1位的值相等，则模式串的“第i+1位的公共前缀长度+1”位的值与主串的当前位置的值肯定不相等
//                   也就没有比较的必要了。
// getNextval改进方法：直接用模式串的“第i+1位的各级的公共前缀长度+1”位的值依次与主串当前位置的值，比较。直到“某一级公共前缀长度+1”位的值与第i+1位的值不同时
//                    将next[i+1]置为“某一级公共前缀长度+1”位即可。或者一直比较到第1位也就是next数组中取出的值是0时还相等，就将next[i+1]置为0

// getNextval函数简介
// 整体与getNext相似，此处只讲区别
// 若j == 0 || t.ch[i] == t.ch[j]条件满足之后i++ j++ 将i移动到了当前正在与主串比较的位置上，j也变为了此时“第i位的公共前缀长度+1”的位置
// 此时比较t.ch[i] 与 t.ch[j]的值就能等得到“第i位的公共前缀长度+1位”的值是否与当前第i位的值相等。
// 因为nextval数组是从低位向高位增长的，能保证每一个位置的"公共前缀长度+1"也就是next数组的值都是经过上述过程优化的最优解，所以此时若相等直接将
// nextval[i]的值设为nextval[j]。若不相等就与getNext数组的处理方法一致了
func getNextval(t SString) []int {
	// t.ch从索引为1的位置开始
	nextval := make([]int, t.length+1)
	nextval[1] = 0
	i, j := 1, 0
	for i < t.length {
		if j == 0 || t.ch[i] == t.ch[j] {
			i++
			j++
			if t.ch[i] != t.ch[j] {
				nextval[i] = j
			} else {
				nextval[i] = nextval[j]
			}
		} else {
			j = nextval[j] // 若不相等时，寻找较低一级的公共前后缀长度+1的值
		}
	}
	return nextval
}
